package construction

type LRUCache struct {
	m               map[int]*Node
	head            *Node
	tail            *Node
	count, capacity int
}

type Node struct {
	key, val  int
	pre, next *Node
}

func putInto(pre,next,target *Node){
	pre.next=target
	target.pre=pre
	next.pre=target
	target.next=next
}

func deleteNode(node *Node)  {
	pre,next:=node.pre,node.next
	pre.next = next
	next.pre = pre
}

func Constructor3(capacity int) LRUCache {
	//弄两个哨兵节点
	head, tail := new(Node), new(Node)
	head.next = tail
	tail.pre = head
	return LRUCache{
		m:        make(map[int]*Node),
		tail:     tail,
		head:     head,
		count:    0,
		capacity: capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	node, ok := this.m[key]
	if !ok {
		return -1
	} else {
		//抽出放到tail位置
		//抽出
		deleteNode(node)
		//放链尾
		putInto(this.tail.pre,this.tail,node)
	}
	return node.val
}

func (this *LRUCache) Put(key int, value int) {
	node, ok := this.m[key]
	//存在则更新
	if ok {
		//抽出
		deleteNode(node)
		//放链尾
		putInto(this.tail.pre,this.tail,node)
		node.val = value
	} else {
		//满了删队首
		if this.count == this.capacity {
			//从链表和哈希表里都删除
			delete(this.m, this.head.next.key)
			deleteNode(this.head.next)
			this.count--
		}
		node = &Node{
			key: key,
			val: value,
		}
		putInto(this.tail.pre,this.tail,node)
		this.m[key] = node
		this.count++
	}
}
